#! /usr/bin/env python
import heapq

DEBUG = True

class Cidade:
    """ Representacao de uma cidade. """
    def __init__(self, estimativa, nome):
        self.estimativa = estimativa
        self.vizinhos = {}
        self.nome = nome
    
    def add_vizinho(self, vizinho, distancia):
        self.vizinhos[vizinho] = distancia
        vizinho.vizinhos[self] = distancia
        return self
    
    def __repr__(self):
         return self.nome

class Visita:
    """
    Representa uma visita feita durante um encaminhamento.

    Cada visita armazena o caminho percorrido, vizinhos que aquele no ainda
    pode visistar, estimativa ao destino (h(x)) e custo do encaminhamento ate
    atingir aquele no (g(x)).
    """ 
    def __init__(self, cidade, caminho, vizinhos, custo, estimativa):
        self.cidade = cidade
        self.caminho = caminho
        self.vizinhos = vizinhos
        self.estimativa = estimativa
        self.custo = custo
    
    def __cmp__(self, other):
        return (self.estimativa + self.custo) - (other.estimativa + other.custo)
    
    def __repr__(self):
        return repr(self.cidade) + ":" + str(self.estimativa + self.custo)

def inicializa_cidades():
    cidades = {}
    for i, estimativa in enumerate([240, 186, 182, 163, 170, 150, 165, 139, 120, \
                       130, 122, 104, 100, 77, 72, 65, 65, 0]):
        nome = chr(ord('a') + i)
        cidades[nome] = Cidade(estimativa, nome)
    return cidades 

def _adiciona_vizinhos(cidades, nome_cidade, vizinhos):
    for nome, distancia in vizinhos:
        cidades[nome_cidade].add_vizinho(cidades[nome], distancia)

def inicializa_rotas(cidades):
    _adiciona_vizinhos(cidades, 'a', [('b', 73), ('c', 64), ('d', 89), ('e', 104)])
    _adiciona_vizinhos(cidades, 'b', [('k', 83)])
    _adiciona_vizinhos(cidades, 'c', [('i', 64)])
    _adiciona_vizinhos(cidades, 'd', [('n', 89)])
    _adiciona_vizinhos(cidades, 'e', [('j', 40)])
    _adiciona_vizinhos(cidades, 'f', [('i', 31), ('n', 84)])
    _adiciona_vizinhos(cidades, 'g', [('j', 35), ('q', 113)])
    _adiciona_vizinhos(cidades, 'h', [('k', 35), ('l', 36)])
    _adiciona_vizinhos(cidades, 'i', [('l', 28), ('m', 20)])
    _adiciona_vizinhos(cidades, 'j', [('n', 53), ('g', 35), ('q', 80)])
    _adiciona_vizinhos(cidades, 'l', [('p', 63)])
    _adiciona_vizinhos(cidades, 'm', [('o', 50)])
    _adiciona_vizinhos(cidades, 'o', [('p', 41), ('r', 72)])
    _adiciona_vizinhos(cidades, 'p', [('r', 65)])
    _adiciona_vizinhos(cidades, 'q', [('r', 65)])


def main():
    cidades = inicializa_cidades()
    inicializa_rotas(cidades)
    visitas = []
    visitas.append(Visita(cidades['a'], \
                          [cidades['a']], \
                          dict(cidades['a'].vizinhos), \
                          0, \
                          cidades['a'].estimativa)) # Origem: cidade 'a'
    
    while visitas[0].cidade != cidades['r']: # Destino: cidade 'r'
        if DEBUG:
            visitas_str = list(visitas)
            visitas_str.sort()
            print visitas_str
        visita_atual = heapq.heappop(visitas)
        for vizinho in visita_atual.vizinhos:
            novos_vizinhos = dict(vizinho.vizinhos)
            novos_vizinhos.pop(visita_atual.cidade)
            novo_caminho = visita_atual.caminho + [vizinho]
            nova_visita = Visita(vizinho, \
                                  novo_caminho, \
                                  novos_vizinhos, \
                                  visita_atual.custo + visita_atual.vizinhos[vizinho], \
                                  vizinho.estimativa)
            heapq.heappush(visitas, nova_visita)
            melhor_caminho = visitas[0].caminho
    
    print melhor_caminho
    
if __name__ == '__main__':
    main()